package com.zhugang.week13.array;

/**
 * @program algorithms
 * @description: SortColors
 * @author: chanzhugang
 * @create: 2022/09/18 14:47
 */
public class SortColors {

    /**
     * 75 颜色分类
     * https://leetcode.cn/problems/sort-colors/
     *
     * @param nums
     */
    public void sortColors(int[] nums) {
        // 荷兰国旗问题
        // 两次双指针：第一次把2放到后面去；第二次把0放前面

        int p = 0;
        int q = nums.length - 1;
        while (p < q) {
            if (nums[p] != 2) {
                p++;
                continue;
            }
            if (nums[q] == 2) {
                q--;
                continue;
            }
            // p是2，q不是2的时候交换，把2换到后面
            swap(nums, p, q);
            p++;
            q--;
        }

        int i = 0;
        int j = p;
        if (nums[j] == 2) {
            // 小细节处理
            j--;
        }
        while (i < j) {
            // 把0换到前面，1换到后面
            if (nums[i] == 0) {
                i++;
                continue;
            }
            if (nums[j] == 1) {
                j--;
                continue;
            }
            // i是1，j是0，把0换到前面
            swap(nums, i, j);

        }
    }

    private void swap(int[] nums, int p, int q) {
        int temp = nums[p];
        nums[p] = nums[q];
        nums[q] = temp;
    }

    // 直接用排序算法
    public void sortColors2(int[] nums) {
        // 根据题意：可以直接使用插入排序、或者快排
        for (int i = 1; i < nums.length; i++) {
            int val = nums[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (nums[j] > val) {
                    // 往后挪一位，并且j前向挪一位
                    nums[j + 1] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + 1] = val;
        }

    }


}